home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / pkscrypt.arc / CRACKER.BAS < prev    next >
BASIC Source File  |  1986-03-21  |  3KB  |  99 lines
  1. 10 REM program to crack the PKSCrypt secret key knowing the public key
  2. 20 REM written by lloyd miller and based on Richard B. Leining's "Hyper"
  3. 30 REM
  4. 40 REM the maximum key length that this program will work properly with is
  5. 50 REM about 8 digits
  6. 60 REM
  7. 70 DEFDBL A-Z
  8. 80 REM
  9. 90 REM program HYPER
  10. 100 REM by Richard B. Leining
  11. 110 REM (From Byte magazine, March 1985, page 396)
  12. 120 REM
  13. 130 PRINT "Hyper factors or tests prime by intersecting"
  14. 140 PRINT "twin hyperbolas x*y = n and (x-1)*(y-1) = fe"
  15. 150 REM read n and (d or e) from a key file
  16. 160 INPUT "keyfile to decode"; KF$
  17. 170 OPEN KF$ FOR INPUT AS #1
  18. 180 LINE INPUT #1, N$
  19. 190 PRINT N$
  20. 200 IF LEFT$(N$, 4) <> "n = " THEN 250
  21. 210 LINE INPUT #1, E$
  22. 220 PRINT E$
  23. 230 IF LEFT$(E$, 4) = "e = " THEN 280
  24. 240 IF LEFT$(E$, 4) = "d = " THEN 280
  25. 250 PRINT "not a key file"
  26. 260 CLOSE 1
  27. 270 GOTO 160
  28. 280 N = VAL(MID$(N$, 5))
  29. 290 CLOSE 1
  30. 300 REM tolerance serves as zero in tests
  31. 310 TOL = .0001#
  32. 320 REM calc consts a and b, scaled down to defer overflow
  33. 330 A = (N + 1) / 2
  34. 340 B = (N - 1) / 2
  35. 350 B = B * B
  36. 360 REM find critical value of fe/4 for two real intersections
  37. 370 FECR4 = (A - ROOT) / 2
  38. 380 FECR4 = INT(FECR4)
  39. 390 REM estimate lowwer bound of fe
  40. 400 MIN% = 3
  41. 410 FEMN4 = A / 2 - (MIN% + N / MIN%) / 4
  42. 420 FEMN4 = INT(FEMN4)
  43. 430 REM predict max reasonable trials for fe
  44. 440 MAX = 1 + FECR4 - FEMN4
  45. 450 PRINT "max reasonable trials = ";INT(MAX)
  46. 460 ALLOW = INT(MAX)
  47. 470 REM upper bound is sometimes a solution for fe. try it fisrt
  48. 480 FE4 = FECR4
  49. 490 TRIAL = 1
  50. 500   REM calc polynomial z (r ^ 2) which is scaled by 1/4
  51. 510   Z = B - FE4 * (A - FE4) * 4
  52. 520   IF Z < 0# THEN 580
  53. 530   REM select perfect square that makes x, y integers
  54. 540   ROOT = SQR(Z)
  55. 550   RDEC = ROOT - INT(ROOT)
  56. 560   IF RDEC <= TOL THEN 640
  57. 570   REM after failure , revise fe/4 for next round
  58. 580   FE4 = FE4 - 1
  59. 590   TRIAL = TRIAL + 1
  60. 600 IF TRIAL <= ALLOW THEN 500
  61. 610 TRIAL = TRIAL - 1
  62. 620 PRINT "can't find the factors of n after"; TRIAL;" trials"
  63. 630 GOTO 970
  64. 640 REM for perfect square, complete calc of x, y
  65. 650 W = A - FE4 * 2
  66. 660 X = W - ROOT
  67. 670 Y = W + ROOT
  68. 680 REM calculate factoring error
  69. 690 ER = INT(X) * INT(Y) - N
  70. 700 PRINT "error = "; ER;
  71. 710 PRINT ", when second hyperbola has fe = "; FE4 * 4
  72. 720 PRINT "factors "; X; Y; " found within"; TRIAL; " trials"
  73. 730 IF ABS(ER) > TOL THEN 570
  74. 740 REM a second distinct solution is unlikely
  75. 750 REM now calculate d for e
  76. 760 REM the rest of this program is written by Lloyd Miller
  77. 770 REM it is based on the code in the genkeys function of PKSCrypt
  78. 780 DIM X(20), B(20), D(20)
  79. 790 X(0) = (X - 1#) * (Y - 1#)
  80. 800 X(1) = VAL(MID$(E$, 5))
  81. 810 B(0) = 0
  82. 820 B(1) = 1
  83. 830 I = 2
  84. 840   REM loop to find e from d and factors of n
  85. 850   D(I) = INT(X(I - 2) / X(I - 1))
  86. 860   X(I) = X(I - 2) - D(I) * X(I - 1)
  87. 870   B(I) = B(I - 2) + D(I) * B(I - 1)
  88. 880   IF X(I) <= 1 THEN 910
  89. 890   I = I + 1
  90. 900   GOTO 840
  91. 910 REM found
  92. 920 PRINT"the other key for this pair is ";
  93. 930 IF I <> INT(I / 2) * 2 THEN 960
  94. 940 PRINT X(0) - B(I)
  95. 950 GOTO 970
  96. 960 PRINT B(I)
  97. 970 END
  98. er key for this pair is ";
  99. 930 IF I <> INT(I / 2) * 2 THEN